package 回溯.不熟;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 解数独.java
 * @createTime 2022年11月08日 19:55:00
 */
public class 解数独 {
	//记录每个3*3小方块是否取到那个数
	boolean[][][] block = new boolean[3][3][9];
	//记录每行中是否可以去到对应的数字
	boolean[][] column = new boolean[9][9];
	//记录每列是否可以去到对应的数字
	boolean[][] line = new boolean[9][9];

	//记录空格的位置，没有填充数字的位置
	List<int[]> spaces = new ArrayList<>();

	//是否遍历完
	boolean valid=false;

	public void solveSudoku(char[][] board) {
		//记录当前每个位置的值
		//遍历行
		for (int i = 0; i < 9; i++) {
			//遍历列
			for (int j = 0; j < 9; j++) {
				if (board[i][j] == '.') {
					spaces.add(new int[] {i, j});
				} else {
					int x = board[i][j] - '0' - 1;
					//是数字的话，需要修改上面创建好的数组
					line[i][x] = column[j][x] = block[i / 3][j / 3][x] = true;
				}
			}
		}
		backTrace(board, 0);
	}

	public void backTrace(char[][] board, int pos) {
		if (pos == spaces.size()) {
			valid = true;
			return;
		}
		int[] arr = spaces.get(pos);
		int i = arr[0], j = arr[1];
		// 从9个数字中选
		for (int digit = 0; digit < 9 && !valid; digit++) {
			//判断是否已经使用
			if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
				line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
				board[i][j] = (char)(digit + '0' + 1);
				//下一行
				backTrace(board, pos + 1);
				line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
			}
		}
	}

	public static void main(String[] args) {
		System.out.println(convertSimpleStr("宝蓝色【杀菌消毒 多功能干衣机】,【机械自动干衣】14烤漆管（无轮）"));
	}

	public static String convertSimpleStr(String str) {
		return str.replaceAll("，", "").replaceAll(",", "").
				replaceAll(" ", "");
	}
}
